
//2055.蜡烛之间的盘子
class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        //根据题意要确定一个区间中蜡烛的个数就需要确定:区间中最外侧盘子的位置,盘子内部蜡烛的个数
        //所以需要使用三个前缀和来解决.
        //记录从前往后到i位置前面最近的位置位置;记录从后往前到i位置后面最近的盘子位置
        //记录从前往后到i位置蜡烛的个数

        int n = s.size(),m=queries.size();
        vector<int> prev(n,-1),back(n,-1),count(n); //三个前缀和
        if(s[0] == '|') prev[0] = 0,count[0] = 1;
        if(s[n-1] == '|') back[n-1] = n-1; 
        for(int i = 1;i < n;i++)
        {
            if(s[i] == '*' ) prev[i] = prev[i-1];
            else prev[i] = i;

            if(s[n-1-i]=='*') back[n-1-i] = back[n-i];
            else back[n-1-i] = n-1-i;
            count[i] += count[i-1] + (s[i]=='*');   //记录蜡烛个数
        }
        vector<int> ret(m);
        for(int i = 0;i < m;i++)
        {
            int a = queries[i][0],b = queries[i][1];
            int end = prev[b],start = back[a];          //最近盘子的位置
            int num = 0;
            if(end != -1&&start != -1&&end > start + 1) num = count[end-1]-count[start];    //盘子之间蜡烛的个数
            ret[i] = num;
        }
        return ret;
    }
};